#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "../include/file_descriptor.h"
#include "../include/bst.h"
#include "../include/narray.h"

/*int main()
{
struct file_descriptor dummy;
NODE* root;
char str[100];
int x,n,i;
char c;
root=NULL;
printf("enter no. of elements:");
scanf("%d",&n);
strcpy(dummy.file_name,"dummy");
strcpy(dummy.file_type,"txt");
dummy.file_size=0;
dummy.start_block_address=0;
dummy.descriptor_address=0;
dummy.dir_descriptors=0;
struct file_descriptor* ptr; 
ptr=&dummy; 
printf("enter tree data:");
c=getchar();
for(i=0;i<n;i++)
{
printf("\nenter a string:");
gets(str);
root=insertAVL(root,str,strlen(str),ptr);
}
root=deleteAVL(root,"vrinda");
printf("\npreorder:\n");
preorder(root);
printf("\ninorder:\n");
inorder(root);
printf("\npostorder:\n");
postorder(root);
}*/

NODE* insert_into_BST(struct  file_descriptor* fp,char path[])
{

char file_path[100];
	
	strcpy(file_path,path);
	if(strcmp(path,"/")!=0)strcat(file_path,"/");
	strcat(file_path,fp->file_name);
	avl_root=insertBST(avl_root,file_path,fp);
return avl_root;
}

NODE* insertBST(NODE* T,char name[],  struct  file_descriptor* p)
{
if(T==NULL)
{
	T=(NODE*)malloc(sizeof(NODE));
	strcpy(T->path,name);
	T->left=NULL;
	T->right=NULL;
	T->fd=p;
}
else if(strcmp(T->path,name)<0)
{
	T->right=insertBST(T->right,name,p);
	if(BF(T)==-2)
	if(strcmp(T->right->path,name)<0)
	T=RR(T);
	else
	T=RL(T);
}
else if(strcmp(T->path,name)>0)
{
	T->left=insertBST(T->left,name,p);
	if(BF(T)==2)
	if(strcmp(T->left->path,name)>0)
	T=LL(T);
	else
	T=LR(T);
}
T->ht=height(T);
return T;
}

//*****************************************************

int height(NODE* T)
{
int lh,rh;
if(T==NULL)
return 0;
if(T->left==NULL)
lh=0;
else 
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
if(lh>rh)
return lh;
return rh;
}

int BF(NODE* T)
{
int lh,rh;
if(T==NULL)return 0;
if(T->left==NULL)lh=0;
else lh=1+T->left->ht;
if(T->right==NULL)rh=0;
else rh=1+T->right->ht;
return (lh-rh);
}

//**********************

NODE* RR(NODE* T)
{
T=rotateleft(T);
return T;
}

NODE* LL(NODE* T)
{
T=rotateright(T);
return T;
}

NODE* LR(NODE* T)
{
T->left=rotateleft(T->left);
T=rotateright(T);
return T;
}

NODE* RL(NODE* T)
{
T->right=rotateright(T->right);
T=rotateleft(T);
return T;
}

//********************************

void postorder(NODE* T)
{
if(T!=NULL)
{
	postorder(T->left);
	postorder(T->right);
	puts(T->path);
}
}

void preorder(NODE* T)
{
if(T!=NULL)
{
	puts(T->path);
	preorder(T->left);
	preorder(T->right);
}
}

void inorder(NODE* T)
{
if(T!=NULL)
{
	inorder(T->left);
	puts(T->path);
	inorder(T->right);
}
}

//*****************************

NODE* rotateright(NODE* x)
{
NODE* y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return y;
}

NODE* rotateleft(NODE* x)
{
NODE* y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return y;
}

//****************************************************************
int searchBST(NODE* s,char name[],int length)
{
  struct node* temp;
  temp = Searchnarray(name);
  if(temp == NULL)
    return 0;
  else
    return 1;
}


int searchBST1(NODE* s,char name[],int length)
{
int valid=0;
if(s==NULL)
return 0 ;
else
{
	if(strcmp(s-> path,name)==1){	
			if(s->left!=NULL)
			valid=searchBST1(s->left,name,strlen(name));
	}
	else if(strcmp(s->path,name)==-1){
			if(s->right!=NULL)
			valid=searchBST1(s->right,name,strlen(name));	
	}
	else valid=1;
}
return valid;
}

void mountBST(struct file_descriptor_list* FDList)
{

avl_root = NULL;
struct file_descriptor dummyFD;
strcpy(dummyFD.file_name, "");
insert_into_BST(&dummyFD, "/");
struct  file_descriptor* fp;
struct file_descriptor_list* temp ;
temp=FDList->next;
char file_path[100];
if(temp!=NULL)
{
	//fp=&(temp->fdescriptor);
	//strcpy(file_path,temp->fpath);
	//if(strcmp(temp->fpath,"/")!=0)strcat(file_path,"/");
	//strcat(file_path,fp->file_name);
	//avl_root=insert_into_BST(fp,file_path);
	while (temp!=NULL)
	{
	fp=&(temp->fdescriptor); 
	strcpy(file_path,temp->fpath);
	//if(strcmp(temp->fpath,"/")!=0)strcat(file_path,"/");
	//strcat(file_path,fp->file_name);
	avl_root=insert_into_BST(fp,file_path);
	temp=temp->next;
	}
}
//printf( "%s\n", "mountAVL() done" ) ;
}

//******************************************************************

NODE* deleteBST(NODE* tree_root, char pathname[]){
  
   NODE* temp=tree_root;
   NODE* del_NODE; 
   NODE* parent_NODE;
   int diff;

   if(tree_root==NULL){
//    printf("Cannot perform deletion on an empty tree!!\n\n");
    return NULL;
   }
   
   diff=strcmp(pathname,tree_root->path);

   while(temp!=NULL && diff!=0){
    parent_NODE = temp;
    if(diff<0)
      temp = temp->left;
    else
      temp = temp->right;
    diff = strcmp(pathname,temp->path);
  }
 
   if(temp==NULL)
    printf("Element not found!\n");
 
   else{ //temp points to the NODE  to be deleted

     del_NODE = temp;

     if(del_NODE==tree_root) { //NODE to be deleted is the root 
  
         if(del_NODE->left==NULL && del_NODE->right==NULL){ //root has no children
              free(del_NODE);
              return NULL;
         }

         else if(del_NODE->left!=NULL && del_NODE->right==NULL)  //root has a left child only
            tree_root = tree_root->left;

         else if(del_NODE->left==NULL && del_NODE->right!=NULL)  //root has a right child only
            tree_root = tree_root->right;

         else{ //root has 2 children
            NODE* prev = tree_root;
            temp = temp->right;
            while(temp->left!=NULL){ //finding the NODE to replace the root
             prev = temp;
             temp = temp->left;
            }
            
            temp->left = tree_root->left;
            if(prev!=del_NODE){
             prev->left = temp->right;
             temp->right = tree_root->right;
            }
            tree_root = temp;

          }
   
     }

     else if(del_NODE==parent_NODE->left){ //NODE to be deleted is a left child
        
        if(del_NODE->left==NULL && del_NODE->right==NULL)  //NODE to be deleted has no children
            parent_NODE->left = NULL;
        
        else if(del_NODE->left!=NULL && del_NODE->right==NULL) //NODE to be deleted has a left child only
            parent_NODE->left = del_NODE->left;
        
        else if(del_NODE->left==NULL && del_NODE->right!=NULL)  //NODE to be deleted has a right child only
            parent_NODE->left = del_NODE->right;

        else{ //NODE to be deleted has 2 children
            NODE* prev = del_NODE;
            temp = temp->right;
            while(temp->left!=NULL){ //finding the NODE to replace the NODE to be deleted
             prev = temp;
             temp = temp->left;
            }
            parent_NODE->left = temp; 
            temp->left = del_NODE->left;
            if(prev!=del_NODE){
             prev->left = temp->right;
             temp->right = del_NODE->right;
            }

          }
 
     }

     else{   //NODE to be deleted is a right child

       if(del_NODE->left==NULL && del_NODE->right==NULL)  //NODE to be deleted has no children
            parent_NODE->right = NULL;

       else if(del_NODE->left!=NULL && del_NODE->right==NULL) //NODE to be deleted has a left child only
            parent_NODE->right= del_NODE->left;

       else if(del_NODE->left==NULL && del_NODE->right!=NULL)  //NODE to be deleted has a right child only
            parent_NODE->right = del_NODE->right;
       
       else{ //NODE to be deleted has 2 children
            NODE* prev = del_NODE;
            temp = temp->right;
            while(temp->left!=NULL){ //finding the NODE to replace the NODE to be deleted
             prev = temp;
             temp = temp->left;
            }
            parent_NODE->right = temp; 
            temp->left = del_NODE->left;
            if(prev!=del_NODE){
             prev->left = temp->right;
             temp->right = del_NODE->right;
            }

         } 

     }    
    
     free(del_NODE); //deleting the NODE
  }
     return tree_root;

}


